//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
//
//
// 示例 2：
//
//
//输入：head = [1], n = 1
//输出：[]
//
//
// 示例 3：
//
//
//输入：head = [1,2], n = 1
//输出：[1]
//
//
//
//
// 提示：
//
//
// 链表中结点的数目为 sz
// 1 <= sz <= 30
// 0 <= Node.val <= 100
// 1 <= n <= sz
//
//
//
//
// 进阶：你能尝试使用一趟扫描实现吗？
//
// Related Topics 链表 双指针 👍 2724 👎 0


package leetcode.editor.cn;

import leetcode.editor.cn.structure.ListNode;

import java.util.Stack;

/**
 * 删除链表的倒数第 N 个结点
 * @author CodeTheory
 * @date 2023-11-08 23:13:18
 */
public class P19_RemoveNthNodeFromEndOfList{
	 public static void main(String[] args) {
	 	 Solution solution = new P19_RemoveNthNodeFromEndOfList().new Solution();
//		 ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
//         ListNode listNode1 = solution.removeNthFromEnd(listNode, 2);
//		 ListNode listNode = new ListNode(1, new ListNode(2, null));
//         ListNode listNode1 = solution.removeNthFromEnd(listNode, 1);
		 ListNode listNode = new ListNode(1, null);
         ListNode listNode1 = solution.removeNthFromEnd(listNode, 1);

		 System.out.println(listNode1);
	 }

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        Stack<ListNode> stack = new Stack<>();
		ListNode dummy = new ListNode(-1, head);
		ListNode curr = dummy;
		while (curr != null) {
			stack.push(curr);
			curr = curr.next;
		}
		while (n-- > 0) {
			stack.pop();
		}
		ListNode peek = stack.peek();
		peek.next = peek.next.next;
		return dummy.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    // 递归
//private int k = 1;
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        if (head == null) return head;
//        ListNode listNode = removeNthFromEnd(head.next, n);
//        if (k++ == n) {
//            return listNode;
//        } else {
//            head.next = listNode;
//        }
//        return head;
//    }
	// 双指针
//public ListNode removeNthFromEnd(ListNode head, int n) {
//	ListNode prev = new ListNode(-1, head);
//	ListNode slow = prev, fast = prev;
//	while (n-- >= 0) {
//		fast = fast.next;
//	}
//
//	while(fast != null) {
//		slow = slow.next;
//		fast = fast.next;
//	}
//	// 删除节点
//	slow.next = slow.next.next;
//
//	return prev.next;
//}

}